|
In graph theory, the Dulmage–Mendelsohn decomposition is a partition of the vertices of a bipartite graph into subsets, with the property that two adjacent vertices belong to the same subset if and only if they are paired with each other in a perfect matching of the graph. It is named after A. L. Dulmage and Nathan Mendelsohn, who published it in 1958. ==The coarse decomposition== Let ''G'' = (''U'',''V'',''E'') be a bipartite graph, and let ''D'' be the set of vertices in ''G'' that are not matched in at least one maximum matching of ''G''. Then ''D'' is necessarily an independent set, so ''G'' can be partitioned into three parts: *The vertices in ''D'' ∩ ''U'' and their neighbors *The vertices in ''D'' ∩ ''V'' and their neighbors *The remaining vertices Every maximum matching in ''G'' consists of matchings in the first and second part that match all neighbors of ''D'', together with a perfect matching of the remaining vertices. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Dulmage–Mendelsohn decomposition」の詳細全文を読む スポンサード リンク
|